package com.sise.Recursion;

import com.sise.Tree.TreeNode;

/**
 *  网址：https://lyl0724.github.io/2020/01/25/1/
 *
 *  递归总结：
 *      以 104. 二叉树的最大深度 作为讲解
 *
 *      1、找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为 0，递归就结束了。
 *      2、找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，
 *                  因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。
 *      3、本级递归应该做什么。
 *                  首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，
 *                  其中根据第二步，root.left 和 root.right 分别记录的是 root 的左右子树的最大深度。
 *                  那么本级递归应该做什么就很明确了，自然就是在 root 的左右子树中选择较大的一个，再加上 1 就是以 root 为根的子树的最大深度了，然后再返回这个深度即可。
 */
public class Recursion {
    public int maxDepth(TreeNode root) {

        // 一开始会持续 递归到此处，返回深度 0
        // 终止条件：当树为空时结束递归，并返回当前深度0
        if(root == null){
            return 0;
        }

        //root的左、右子树的最大深度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        //返回的是左右子树的最大深度+1
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
